package com.leetcode;

public class RemoveElement
{
	public static void main(String[] args)
	{
		int A[] = {1,2,3,3,4,3,3,5,3,3,6,3,3,3,7,3,3,3,3,3,3};
		int n = removeElement(A,3);
		for (int i = 0; i <n; i++)
		{
			System.out.println(A[i]);
		}
		
	}

	public static int removeElement(int[] A, int elem)
	{
		int n = A.length;

		int i = 0;
		int j = n;

		while (i < j)
		{
			if (A[i] == elem)
			{
				// search from back to front, find a element
				// that is not t to change with A[i]
				while (--j > i && A[j] == elem)
					;
				// No element in the remain of array is not t,
				// stop searching.
				if (j <= i)
					break;
				else
					// switch two elements to move t to the back of array
					A[i] = A[j];
			}

			++i;
		}

		return i;
	}
}
